Recently, there has been an increasing number of opportunities for digital contents such as a document, image data, etc. to be distributed through large-capacity recording media such as a communication line, a DVD, etc. A digital contents delivery service distributes contents to specific users, and requires a system not to reveal the contents to other people than the specific users. In the delivery of contents through large-capacity media, a mechanism for similarly controlling access by users has been developed. In this case, contents data has been encrypted, scrambled, etc., and there has been provided a system in which only authorized users informed of valid key information or de-scrambling process can perform a decoding process and legally use the contents such as the documents, image data, etc.
In the contents delivery service, there is a contents provider for distributing the contents. It is necessary for the contents provider to set different pieces of access control information for the respective contents, and it is assumed that an encrypting process is to be performed using a different key for each content, user, and user action (for example, browsing, copying, etc.). In this process, the management of the key information about key generation, key holding, key delivery, etc. puts a heavy load on a contents provider in many cases. Therefore, relating to the key management, there has been a study on the way to efficiently manage a key without degrading the security level. Described below are some conventional managing methods.
[Tree Structure Management Method]
The tree structure management method is used by contents regeneration equipment in an off-line mode of a DVD player, etc., and is suitable for performing nullification of users. In this method, the key information and encrypted contents used in the encrypting process are simultaneously delivered or stored in a medium so that only an authorized user can decode the encrypted data. Although it is necessary to deliver key information in advance using an appropriate combination for each user, the tree structure allows an enormously large amount of user key information to be efficiently managed.
In the management method, there are the following indices for determining a method is good or bad. They are: 1) data size of the key information delivered with contents; 2) data size of the key information delivered in advance and held by a user; and 3) data size of the key information to be managed by a contents provider. In the case of the online delivery service, the index 1) on which the network traffic depends is regarded. However, from the viewpoint of the contents provider, the management cost of the index 3) is regarded with the highest priority. Thus, it is important to consider the change in weight of the index depending on the situation.
A typical tree structure management method is a contents delivery model (for example, refer to the Non-Patent Document 1). This model uses a tree structure for key delivery as shown in FIG. 44, and a different key is assigned to each node. A user key (a key held by a player such as a DVD in the document) is identified as a terminal node (leaf node), and it is assumed that all key data from the root to the terminal node are held. In this model, it is assumed that data is frequently updated, and the efficiency of nullifying a key can be improved with the above-mentioned configuration.
[Hierarchical Key Management Method]
On the other hand, the key management assumed in the hierarchical key management method is identical in assigning a key to each node, but it is greatly different in that keys assigned to all nodes including the root, not only a terminal node, are delivered to the user (for example, refer to the Non-Patent Documents 2 and 3).
Unlike the n-ary tree as shown in FIG. 44, an access structure as shown in FIGS. 45 and 46 is assumed, and there is a portion where the relationship as shown in FIG. 47 is locally detected. In this case, it is necessary to provide a system capable of generating a key to be held by a node n3 from both key assigned to a node n1 and key assigned to a node n2. According to the document of Birget et al. (Non-Patent Document 3), the methods for providing the system can be the following two methods proposed.
[(1) User Multiple Keying]
Each node holds plural keys, and a parent node is designed to have all keys of a child node. FIG. 48 shows an example, and shows a set of key data delivered to each node. For example, the parent node of a node to which {k5} is delivered includes the key data k5. Similarly, in other nodes, a parent node includes all key data of its child node.
[(2) One-way Function Based Keying Schemes]
A method obtained by extending the proposition (Non-Patent Document 2) of Lin et al., and the key information held by each node can be reduced using a one-way hash function. However, when the key data of a child node is generated from the key data of plural parent nodes as shown in FIG. 47, the following operations are required. The operations are explained below by referring to FIG. 49.
In FIG. 49, to generate key data k3 from key data k1 or k2, the following arithmetic operations are performed.k3:=F(k1,n3) XOR r13k3:=F(k2,n3) XOR r23
where “XOR” indicates an exclusive OR for each bit, and “F( )” indicates a one-way hash function and is described later in detail. “n3” indicates an identifier of a node associated with the key data k3, “r13” and “r23” respectively indicate the random data associated with the node n1 (key data k1) and the node n3, and the random data associated with the node n2 (key data k2) and the node n3, both of which are published.
The function F( ) is constituted by F(k_i, n_j)=g^{k_i+n_j}mod p (where “p” indicates a prime number, and “g” indicates a source), and the above-mentioned “r12” and “r13” are generated such that F(k1,n3) XOR r13=F(k2,n3) XOR r23 can be satisfied.
Non-Patent Document 1: “Digital Contents Protective Management Method” SCIS2001, pp. 213-218
Non-Patent Document 2: C. H. Lin. “Dynamic key management schemes for access control in a hierarchy” Computer Communications, 20:1381-1385, 1997
Non-Patent Document 3: J.-C. Birget, X. Zou, G. Noubir, B. Ramamurthy, “Hierarchy-Based Access Control in Distributed Environments” in the Proceedings of IEEE ICC, June 2001